package com.leetcode.dynamic_programming;

/**
 * @author Dennis Li
 * @date 2020/10/10 17:03
 */
public class KMP_28 {

    private int[] createNext(String pattern) {
        // 建立next数组，跳转到有相同前缀的位置再次进行匹配
        int len = pattern.length();
        int[] next = new int[len];
        // 第一位置为-1，原因在匹配里面
        next[0] = -1;
        int i = 0, j = -1;
        // 类似动态规划，next数组的构建其实是自己和自己做了一次匹配的过程
        while (i < len - 1) {
            // 匹配的话则两个指针同时前进
            // 因为如果匹配，表示两个位置的字符相等，而如果可以继续右移的话，那么他的下一位也一定相等，否则将会执行j的回退
            if (j == -1 || pattern.charAt(j) == pattern.charAt(i))
                next[++i] = ++j;
            else
                // 不匹配则由j指针执行回退
                j = next[j];
        }
        return next;
    }

    public int strStr(String text, String pattern) {
        // 注意，模式串为空的判定需要在前面
        if (pattern.equals("")) return 0;
        if (text.equals("")) return -1;
        // 根据模式串构建next数组
        int[] next = createNext(pattern);

        int j = 0, i = 0;
        while (i < text.length()) {
            if (j == pattern.length())
                return i - j;
            // 如果有相同，两个指针都向前进
            // 当j退到最后一位时，变为-1，表明匹配的位置需要整体右移
            if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else {
                // 如果不相同，则j指针回退，i指针不动
                j = next[j];
            }
        }
        // 有可能是在末位完成匹配
        return j == pattern.length() ? text.length() - pattern.length() : -1;
    }

    static class Solution {
        public int strStr(String text, String pattern) {
            int[] next = createNext(pattern);
            next[0] = -1;
            int i = 0, j = 0;
            while (i < text.length()) {
                if (j == pattern.length())
                    return i - j;
                if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
                    j++;
                    i++;
                } else {
                    j = next[j];
                }
            }

            return j == pattern.length() ? text.length() - pattern.length() : -1;
        }

        private int[] createNext(String pattern) {
            int len = pattern.length();
            int[] next = new int[len];
            int i = 0, j = -1;
            while (i < pattern.length() - 1) {
                if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
                    next[++i] = ++j;
                } else {
                    j = next[j];
                }
            }
            return next;
        }
    }

}
